package com.gxc.recursion;

/**
 * 两头牛吃草问题
 * 已知牛吃草的数量必然为4的指数级，1 4 16 64 ***
 * 先手牛先吃，后手牛后吃
 * 给定N数量的草，求哪头牛先吃到最后的草
 *    0    后手牛吃到
 *    1    先手牛吃到
 *    2    后手牛吃到
 */
public class CowGraze {

    public static void main(String[] args) {
        for (int i = 0; i < 60; i++) {
            System.out.println("草的数量：" + i + "，赢的牛：" + graze(i));
        }

        System.out.println("----");

        for (int i = 0; i < 60; i++) {
            if (!sumUp(i).equals(graze(i))) {
                System.out.println("结果不一致");
            }
        }
    }

    /**
     *
     * @param n 剩余数量的草
     * @return
     */
    private static String graze(int n) {
        if (n == 0) return "后手";
        if (n == 1) return "先手";
        if (n == 2) return "后手";
        if (n == 3) return "先手";
        if (n == 4) return "先手";

        //如果发现吃不完，则尝试吃4的指数
        int once = 1;
        for (int i = 1; once<=n; i++) {
            //n - once  剩余草的数量
            String result = graze(n - once);
            if (result.equals("后手")) {
                return "先手";
            }
            //防止越界
            if (n/once < 4) break;
            //草的数量循环吃4的指数
            once = once*4;
        }

        return "后手";
    }

    private static String sumUp(int n) {
        n = n%5;
        return (n ==0 || n ==2)?"后手":"先手";
    }
}
